{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Coin Change Problem\n",
    "\n",
    "**Note: This problem has multiple solutions and is a classic problem in showing issues with basic recursion. There are better solutions involving memoization and simple iterative solutions.If you are having trouble with this problem (or it seems to be taking a long time to run in some cases) check out the Solution Notebook and fully read the conclusion link for a detailed description of the various ways to solve this problem!**\n",
    "\n",
    "\n",
    "This problem is common enough that is actually has its own [Wikipedia Entry](https://en.wikipedia.org/wiki/Change-making_problem)! Let's check the problem statement again:\n",
    "\n",
    "This is a classic recursion problem: Given a target amount **n** and a list (array) of distinct coin values, what's the fewest coins needed to make the change amount. \n",
    "\n",
    "For example:\n",
    "\n",
    "If n = 10 and coins = [1,5,10]. Then there are 4 possible ways to make change:\n",
    "\n",
    "* 1+1+1+1+1+1+1+1+1+1\n",
    "\n",
    "* 5 + 1+1+1+1+1\n",
    "\n",
    "* 5+5\n",
    "\n",
    "* 10\n",
    "\n",
    "With 1 coin being the minimum amount.\n",
    "\n",
    "    \n",
    "## Solution\n",
    "\n",
    "This is a classic problem to show the value of dynamic programming. We'll show a basic recursive example and show why it's actually not the best way to solve this problem.\n",
    "\n",
    "Make sure to read the comments in the code below to fully understand the basic logic!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rec_coin(target,coins):\n",
    "    '''\n",
    "    INPUT: Target change amount and list of coin values\n",
    "    OUTPUT: Minimum coins needed to make change\n",
    "    \n",
    "    Note, this solution is not optimized.\n",
    "    '''\n",
    "    \n",
    "    # Default to target value\n",
    "    min_coins = target\n",
    "    \n",
    "    # Check to see if we have a single coin match (BASE CASE)\n",
    "    if target in coins:\n",
    "        return 1\n",
    "    \n",
    "    else:\n",
    "        \n",
    "        # for every coin value that is <= than target\n",
    "        for i in [c for c in coins if c <= target]:\n",
    "            \n",
    "            # Recursive Call (add a count coin and subtract from the target) \n",
    "            num_coins = 1 + rec_coin(target-i,coins)\n",
    "            \n",
    "            # Reset Minimum if we have a new minimum\n",
    "            if num_coins < min_coins:\n",
    "                \n",
    "                min_coins = num_coins\n",
    "                \n",
    "    return min_coins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see it in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec_coin(63,[1,5,10,25])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The problem with this approach is that it is very inefficient! It can take many, many recursive calls to finish this problem and its also inaccurate for non standard coin values (coin values that are not 1,5,10, etc.)\n",
    "\n",
    "We can see the problem with this approach in the figure below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"http://interactivepython.org/runestone/static/pythonds/_images/callTree.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "Image(url='http://interactivepython.org/runestone/static/pythonds/_images/callTree.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each node here corresponds to a call to the **rec_coin** function. The label on the node indicated the amount of change for which we are now computng the number of coins for. Note how we are recalculating values we've already solved! For instance 15 is called 3 times. It would be much better if we could keep track of function calls we've already made.\n",
    "_____\n",
    "## Dynamic Programming Solution\n",
    "\n",
    "This is the key to reducing the work time for the function. The better solution is to remember past results, that way before computing a new minimum we can check to see if we already know a result.\n",
    "\n",
    "Let's implement this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rec_coin_dynam(target,coins,known_results):\n",
    "    '''\n",
    "    INPUT: This funciton takes in a target amount and a list of possible coins to use.\n",
    "    It also takes a third parameter, known_results, indicating previously calculated results.\n",
    "    The known_results parameter shoud be started with [0] * (target+1)\n",
    "    \n",
    "    OUTPUT: Minimum number of coins needed to make the target.\n",
    "    '''\n",
    "    \n",
    "    # Default output to target\n",
    "    min_coins = target\n",
    "    \n",
    "    # Base Case\n",
    "    if target in coins:\n",
    "        known_results[target] = 1\n",
    "        return 1\n",
    "    \n",
    "    # Return a known result if it happens to be greater than 1\n",
    "    elif known_results[target] > 0:\n",
    "        return known_results[target]\n",
    "    \n",
    "    else:\n",
    "        # for every coin value that is <= than target\n",
    "        for i in [c for c in coins if c <= target]:\n",
    "            \n",
    "            # Recursive call, note how we include the known results!\n",
    "            num_coins = 1 + rec_coin_dynam(target-i,coins,known_results)\n",
    "            \n",
    "            # Reset Minimum if we have a new minimum\n",
    "            if num_coins < min_coins:\n",
    "                min_coins = num_coins\n",
    "                \n",
    "                # Reset the known result\n",
    "                known_results[target] = min_coins\n",
    "                \n",
    "    return min_coins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target = 74\n",
    "coins = [1,5,10,25]\n",
    "known_results = [0]*(target+1)\n",
    "\n",
    "rec_coin_dynam(target,coins,known_results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "Run the cell below to test your function against some test cases. \n",
    "\n",
    "**Note that the TestCoins class only test functions with two parameter inputs, the list of coins and the target**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR FUNCTION.\n",
    "NOTE: NON-DYNAMIC FUNCTIONS WILL TAKE A LONG TIME TO TEST. IF YOU BELIEVE YOU HAVE A SOLUTION\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestCoins(object):\n",
    "    \n",
    "    def check(self,solution):\n",
    "        coins = [1,5,10,25]\n",
    "        assert_equal(solution(45,coins),3)\n",
    "        assert_equal(solution(23,coins),5)\n",
    "        assert_equal(solution(74,coins),8)\n",
    "\n",
    "        print 'Passed all tests.'\n",
    "        \n",
    "# Run Test\n",
    "\n",
    "test = TestCoins()\n",
    "test.check(rec_coin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion and Extra Resources\n",
    "\n",
    "For homework, read the link below and also implement the non-recursive solution described in the link!\n",
    "\n",
    "For another great resource on a variation of this problem, check out this link:\n",
    "[Dynamic Programming Coin Change Problem](http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
